package com.bo.day20231221;

/**
 * 判断是否为回文链表
 * 实现思路：
 * 找到中点的位置
 *
 * @Author: gpb
 * @Date: 2023/12/21 14:45
 * @Description:
 */
public class IsPalindromeList {
    public static class Node {
        public int value;
        public Node next;

        public Node (int data) {
            this.value = data;
        }
    }

    public static boolean isPalindrome (Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        // 快指针
        Node fast = head.next;
        Node slow = head.next;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        Node p = slow;
        Node pre = null;
        Node next = null;
        while (p != null) {
            // 此时 要记录 p.next的值
            next = p.next;
            // 头指针的下一个接下要只执行上一个节点
            p.next = pre;
            // next 等于当前节点,作为下次循环的上一个节点
            pre = p;
            p = next;
        }
        p = pre;
        // 判断是否一下
        boolean res = true;
        while (head != null && p != null) {
            if (head.value != p.value) {
                res = false;
                break;
            }
            head = head.next;
            p = p.next;
        }
        p = pre;
        next = null;
        Node s = null;
        while (p != null) {
            s = p.next;
            p.next = next;
            next = p;
            p = s;
        }
        return res;
    }

    public static void main (String[] args) {
        IsPalindromeList.Node test = null;
        test = new IsPalindromeList.Node(1);
        test.next = new IsPalindromeList.Node(2);
//        test.next.next = new IsPalindromeList.Node(2);
//        test.next.next.next = new IsPalindromeList.Node(1);
//        test.next.next.next.next = new IsPalindromeList.Node(0);
        System.out.println(isPalindrome(test));


        Node node = new Node(3);
        node.next = new Node(1);
        node.next.next = new Node(5);
        node.next.next.next = new Node(8);
        node.next.next.next.next = new Node(2);

        Node p = node;
        Node H = node;
        Node next = null;
        while (p.next != null) {
            p = p.next;
            H.next = next;
            next = H;
            H = p;
        }
        H.next = next;
        System.out.println(node.value);
        System.out.println(H.value);
    }

}
